package primary.primary0;

import java.util.ArrayList;
import java.util.List;

public class S0022括号生成 {



    /**
     * 76
     * 这方法叫回溯，和树的遍历很像就是了
     * 二叉树，但是分叉以及终止条件需要判断一下
     * 如果是单纯走出2^n个节点，然后再判断是否可行的话，复杂度太高。
     * 就想象一下相邻的两个左右括号会做消消乐，
     * 那么我在放心的括号的时候，可以认为这之前的一串括号，通过消消乐，只剩0~n个左括号了
     * 这时候我可以放什么呢?如果消消乐结果有左括号(剩下的左括号<有括号)那么我可以放左括号/有括号
     * 如果左右相同，我就只能放左括号了，
     * 这样就不会出现右括号>左括号的情况了
     *
     * 终止条件是没有剩余的括号了。
     */
    class Solution {

        // 结果
        public List<String> result;

        // 二叉树，要么放左括号，要么放右括号，然后带一个判断吧
        public List<String> generateParenthesis(int n) {
            result = new ArrayList<>();
            helpMethod(n, n, "");
            return result;

        }

        public void helpMethod(int leftRemain, int rightRemain, String curString){
            // 如果左右括号都用完了，那么要存储起来
            if(leftRemain == 0 && rightRemain == 0){
                result.add(curString);
                return;
            }
            // 如果左右都还剩，那么可以放任何一个


            if(leftRemain != 0 && rightRemain != 0){
                if(leftRemain == rightRemain){
                    // 不允许产生右括号比左括号多的情况，所以左右括号使用量相同的情况下，只能放左括号
                    helpMethod(leftRemain - 1, rightRemain, curString+"(");
                }else{
                    helpMethod(leftRemain - 1, rightRemain, curString+"(");
                    helpMethod(leftRemain, rightRemain - 1, curString+")");
                }

                return;
            }
            // 如果还有左边，没有右边，那么异常 return
            if(leftRemain != 0){
                return;
            }
            // 如果没有左边有右边，放右边
            helpMethod(leftRemain, rightRemain - 1, curString+")");
        }
    }

    /**
     * 和上面一样，但是用StringBuilder做
     */
    class Solution2 {

        // 结果
        public static List<String> result;

        // 二叉树，要么放左括号，要么放右括号，然后带一个判断吧
        public List<String> generateParenthesis(int n) {
            result = new ArrayList<>();
            helpMethod(n, n, "");
            return result;

        }

        public void helpMethod(int leftRemain, int rightRemain, String curString){
            // 如果左右括号都用完了，那么要存储起来
            if(leftRemain == 0 && rightRemain == 0){
                result.add(curString);
                return;
            }
            // 如果左右都还剩，那么可以放任何一个
            if(leftRemain != 0 && rightRemain != 0){
                if(leftRemain == rightRemain){
                    // 不允许产生右括号比左括号多的情况，所以左右括号使用量相同的情况下，只能放左括号
                    helpMethod(leftRemain - 1, rightRemain, curString+"(");
                }else{
                    helpMethod(leftRemain - 1, rightRemain, curString+"(");
                    helpMethod(leftRemain, rightRemain - 1, curString+")");
                }

                return;
            }
            // 如果还有左边，没有右边，那么异常 return
            if(leftRemain != 0){
                return;
            }
            // 如果没有左边有右边，放右边
            helpMethod(leftRemain, rightRemain - 1, curString+")");
        }
    }
}
